Motivated by map services, there has been an abundance of research on determining journeys in transportation networks. Much of the research has focused on computing driving directions on road networks. Existing computer programs known as road-mapping programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Several existing road-mapping products typically include the ability to calculate a best route between two locations. In other words, the user can input two locations, and the road-mapping program will compute the travel directions from the source location to the destination location. The directions are typically based on distance, travel time, etc. Computing the best route between locations may require significant computational time and resources.
Some road-mapping programs compute shortest paths using variants of a well known method attributed to Dijkstra. Note that in this sense “shortest” means “least cost” because each road segment is assigned a cost or weight not necessarily directly related to the road segment's length. By varying the way the cost is calculated for each road, shortest paths can be generated for the quickest, shortest, or preferred routes. Dijkstra's original method, however, is not always efficient in practice, due to the large number of locations and possible paths that are scanned. Instead, many known road-mapping programs use heuristic variations of Dijkstra's method.
More recent developments in road-mapping algorithms utilize a two-stage process comprising a preprocessing phase and a query phase. During the preprocessing phase, the graph or map is subject to an off-line processing such that later real-time queries between any two destinations on the graph can be made more efficiently. The preprocessing phase may take several minutes (or even hours) and computes some auxiliary data, which is later used to accelerate queries. Known examples of preprocessing algorithms use geometric information, hierarchical decomposition, and A* search combined with landmark distances.
Routing in public transportation networks (e.g., planning a journey between two points in a public transportation system starting at a given time) may seem superficially similar, but this problem turns out to be significantly more difficult to deal with. The techniques developed for road networks are of little help for public transit. There are several reasons for this. First, public transit networks do not have the strong hierarchical properties of road networks, where nearly all long distance journeys converge into major freeways. Second, public transportation networks are inherently time-dependent (e.g., buses and trains have schedules which are taken into account when determining the shortest or least cost journey). Third, in addition to travel times, the number of transfers made is also to be considered. This is often done by reporting more than one journey. Additionally, public transit systems are dynamic, with frequent delays and cancellations. Unlike in road networks, small delays can have a huge impact on the resulting routes, because a missed connection may result in waiting at a transit station or stop (e.g., a train station or bus stop) for several hours. There are no conventional techniques known that can handle efficiently the above mentioned features on a transit network of a large metropolitan area.